package leetcode.code292;

/**
 *
 * @author CaoYu
 * @date 2021年9月18日
 * @description
 */
public class Solution2 extends Solution292 {

	@Override
	public boolean canWinNim(int n) {
		boolean dp1 = true;
		boolean dp2 = true;
		boolean dp3 = true;
		if (n == 0)
			return false;
		if (n <= 3)
			return true;
		int i = 4;
		while (i <= n) {
			boolean dpn = false;
			if (!dp3 || !dp2 || !dp1) {
				dpn = true;
			}
			i++;
			dp1 = dp2;
			dp2 = dp3;
			dp3 = dpn;
		}
		return dp3;
	}

	/**
	 * 超出内存限制
	 */
	public boolean canWinNim2(int n) {
		boolean[] dp = new boolean[n + 1];
		int i = 1;
		dp[0] = false;
		while (i <= n) {
			if (i <= 3 || !dp[i - 1] || !dp[i - 2] || !dp[i - 3]) {
				dp[i] = true;
			}
			i++;
		}
		return dp[n];
	}

	/**
	 * 递归超时
	 *
	 * @param n
	 * @return
	 */
	public boolean canWinNim1(int n) {
		if (n <= 3 || !canWinNim(n - 1) || !canWinNim(n - 2) || !canWinNim(n - 3))
			return true;
		return false;
	}

	public boolean canWinNim0(int n) {
		if (n % 4 == 0)
			return false;
		return true;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
		so.debug5();

	}

}
